/*
 * @lc app=leetcode.cn id=279 lang=cpp
 *
 * [279] 完全平方数
 */

// @lc code=start
// 四平方和定理
#include <bits/stdc++.h>
using namespace std;
class Solution
{
    // 判断是否为完全平方数
    bool isPerfectSquare(int x)
    {
        int y = sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    bool checkAnswer4(int x)
    {
        while (x % 4 == 0)
        {
            x /= 4;
        }

        return x % 8 == 7;
    }

public:
    int numSquares(int n)
    {
        if (isPerfectSquare(n))
        {
            return 1;
        }
        if (checkAnswer4(n))
        {
            return 4;
        }
        for (int i = 1; i * i <= n; i++)
        {
            int j = n - i * i;
            if (isPerfectSquare(j))
            {
                return 2;
            }
        }
        return 3;
    }
};
// @lc code=end
